Communication systems such as satellite or mobile communication systems have incorporated therein the error correction coding technology with a large coding gain to meet system requirements for power reduction and small antenna size. A low-density parity-check code is known as an error correcting code having a very large coding gain. The introduction of the low-density parity-check code into various communication systems and storage devices such as magnetic storage devices is presently in progress.
A low-density parity-check coding scheme does not refer to a single error correction coding scheme, but refers to a general term for error correcting codes which are characterized in that they are defined by a sparse check matrix. The sparse check matrix means that most of the components (elements) of the check matrix are “0” and the number of components “1” is very small. As disclosed in D. J. C. Mackay, “Good Error-Correcting Codes Based on very sparse matrices,” IEEE Transactions on Information Theory, pp. 399-431, March 1999 (Non-patent literature 1), the low-density parity-check code is characterized in that it can provide an error correction coding scheme having a very large coding gain close to the theoretical limitation, by employing a repetitive decoding scheme such as a sum-product algorithm based on the selection of a sparse check matrix.
One technical problem with the low-density parity-check code is that it requires a large amount of calculations for a coding process, i.e., a process of calculating a redundant bit sequence from a information bit sequence. In a most typical coding device wherein generation of a redundant bit sequence comprises multiplying calculation of matrices by a code generator matrix, the generation of a low-density parity-check code sequence requires a number of exclusive-ORing operations which is proportional to the square of the code length.
If a coding device comprises a code check matrix, then a check matrix is basically deformed such that a portion of the check matrix becomes a diagonal matrix, as shown by equation (1), and the generation of a low-density parity-check code sequence is realized by the basically deformed check matrix.
                    (                  A          |                                                    1                                                                                                                                                                                                        0                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                                                                            ⋱                                                                                                                                                  0                                                                                                                                                                                                        1                                                    )                            (        1        )            
Specifically, if it is assumed that r and k represent positive integers, i an integer in the range of 1≦i≦r, A in equation (1) an r×k matrix, and c1, c2, . . . , ck an information bit sequence of k bits, then each bit pi of corresponding redundant bit sequence p1, p2, . . . , pr is calculated according to following equation (2):
                              p          i                =                                            ∑                              j                =                1                            k                        ⁢                                          a                                  i                  ,                  j                                            ⁢                              c                j                                              =                                                    a                                  i                  ,                  1                                            ⁢                              c                1                                      +                                          a                                  i                  ,                  2                                            ⁢                              c                2                                      +            …            +                                          a                                  i                  ,                  k                                            ⁢                              c                k                                                                        (        2        )            where j represents an integer in the range of 1≦j≦k and ai,j an (i,j) component of r×k matrix A. In order to carry out coding of an error correcting code, it is necessary to store r×k matrix A in a storage device such as a memory and perform as many exclusive-ORing operations as the number of values “1” in the components of matrix A.
FIG. 1 shows an example of the arrangement of a coding device according to the related art for performing coding by a low-density parity-check code. When the illustrated coding device is given an information bit sequence, it codes the information bit sequence with a low-density parity-check code and outputs a code bit sequence. The coding device comprises redundant bit sequence calculating device 71 for performing the calculation according to equation (2) on the information bit sequence to generate a redundant bit sequence, matrix information storage memory 72 for holding matrix A shown in equation (1) and supplying the components (elements) of matrix A to redundant bit sequence calculating device 71, and switch 73 for selecting, one at a time, the information bit sequence and the redundant bit sequence from redundant bit sequence calculating device 71, for thereby producing a code bit sequence which comprises a combination of the information bit sequence and the redundant bit sequence. Redundant bit sequence calculating device 71 includes exclusive-ORing circuits.
For reducing the storage capacity of the storage device (i.e., matrix information storage memory 72) and reducing the number of exclusive-ORing circuits included in redundant bit sequence calculating device 71, there is known a process of constructing a low-density parity-check code such that the number of “1” in the components of matrix A is as small as possible and a coding gain achieved by repetitive decoding is preferably large. Such a constructing process is disclosed in, for example, Thomas Richardson, R. Urbanke, “Efficient Encoding of Low-Density Parity-Check Codes,” IEEE Transactions on Information Theory, pp. 619-656, September 2001 (Non-patent literature 2). JP-2003-115768A (Patent literature 1) and JP-2004-72130A (Patent literature 2) disclose a process of using a matrix comprising block matrices of a cyclic permutation matrix as a check matrix and limiting each of the block matrices to a cyclic matrix for thereby reducing the storage capacity and simplifying exclusive-ORing operations. A check matrix that is limited in such a manner is specifically referred to as a pseudo-cyclic code. These processes still have a problem in that the reduced apparatus scale and the simplified processing are incompatible. In other words, the processes using the pseudo-cyclic codes require complicated control though the apparatus scale is reduced, or are applicable to further restricted codes among pseudo-cyclic codes, i.e., only codes to which additional restrictive conditions are added.
For the progress of the application of error correction coding to various communication systems and storage devices such as magnetic storage devices, it has been desirable to develop a coding scheme for improving a coding gain obtained by repetitive decoding according to the sum-product algorithm, in addition to a small-scale apparatus for performing a simple coding process.    Patent literature 1: JP-2003-115768A    Patent literature 2: JP-2004-72130A    Non-patent literature 1: D. J. C. Mackay, “Good Error-Correcting Codes Based on very sparse matrices,” IEEE Transactions on Information Theory, pp. 399-431, March 1999    Non-patent literature 2: Thomas Richardson, R. Urbanke, “Efficient Encoding of Low-Density Parity-Check Codes,” IEEE Transactions on Information Theory, pp. 619-656, September 2001